package org.example;

import java.util.Arrays;

public class Test2 {
    //leetcode 有效三角形的个数
    //https://leetcode.cn/problems/valid-triangle-number/description/

    /**
     * 先固定最长的一条边，然后使用双指针确定可以构成三角形的边的区间
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        if (nums.length < 3) return 0;
        Arrays.sort(nums);
        int ret = 0;
        for (int i = nums.length-1; i > 1; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,3,4};
        Test2 test2 = new Test2();
        test2.triangleNumber(nums);
        System.out.println(666);
    }
}
